Switching systems (also referred to as “switching networks”) route data through and among data communications networks. Switching systems typically comprise a plurality of switches and clusters of switches (“nodes”) that provide data communications paths among elements of data communications networks.
The “topology” of a switching network refers to the particular arrangement and interconnections (both physical and logical) of the nodes of a switching network. Knowledge of the topology of a switching network is used to compute communications paths through the network.
For switching systems that comprise a small number of individual switches, the topology is fairly straightforward and can be described by identifying the individual nodes in the system and the communications links between them. For larger and more complex networks, however, the amount of data needed to identify all links between all nodes of the network can be quite extensive.
A number of approaches have been proposed to reduce the amount of information needed to describe the topology of complex switching networks. One approach involves grouping physical nodes into groups (“peer groups”) that are viewed as individual logical nodes (“logical group nodes”) having characteristics that comprise an aggregation of the characteristics of the individual nodes within the group. Such logical group nodes may be further grouped with other physical and/or logical nodes to form successively higher level peer groups, creating a hierarchy of peer groups and logical group nodes.
The PNNI Protocol
One example of a network that allows physical nodes to be grouped into levels of logical groups of nodes is a “PNNI” network. PNNI, which stands for either “Private Network Node Interface” or “Private Network Network Interface,” is a protocol developed by the ATM Forum. The PNNI protocol is used to distribute topology information between switches and clusters of switches within a private ATM switching network. Details of the PNNI protocol can be found in various publications issued by the ATM Forum, including “Private Network Network Interface Specification Version 1.1 (PNNI 1.1),” publication No. af-pnni-0055.002, available at the ATM Forum's website at www.atmforum.com.
A “PNNI network” is a network that utilizes the PNNI protocol. Some basic features of a PNNI network are described below. It should be noted, however, that these features are not exclusive to PNNI networks. The same or similar features may be utilized by networks using other and/or additional protocols as well.
Physical Nodes
FIG. 1 shows an example network 100 comprising twenty-six (26) physical nodes (also referred to as “lowest level nodes”) 105a-z. Nodes 105a-z are interconnected by thirty three (33) bi-directional communications links 110a-gg. 
Although network 100 is relatively small, identifying its topology is already fairly complex. One way that such identification may be accomplished is for each node to periodically broadcast a message identifying the sending node as well as the other nodes that are linked to that node. For example, in network 100 of FIG. 1, node 105a would broadcast a message announcing “I'm node 105a and I can reach nodes 105b and 105x.” Similarly, node 105x would broadcast “I'm node 105x and I can reach nodes 105a, 105w, 105y, and 105z.” Each of the other 24 nodes of network 100 would broadcast similar messages. Each node 105a-z would receive all the messages of all other nodes, store that information in memory, and use that information to make routing decisions when data is sent from that node to another.
Although each node broadcasting its individual connectivity information to all other nodes allows each node in a network to deduce the overall topology of the network, such massive broadcasting, particularly in large networks, consumes a significant amount of network bandwidth. Networks such as PNNI networks reduce this overhead by grouping nodes into a hierarchy of node groups called “peer groups.”
Peer Groups and Logical Nodes
An important concept in PNNI and other networks is a “logical node”. A logical node is viewed as a single node at its level in the hierarchy, although it may represent a single physical node (in the case of the lowest hierarchy level or a single member group) or a group of physical nodes (at higher hierarchy levels). For simplicity, logical nodes are sometimes referred to herein simply as “nodes.” In a PNNI network, logical nodes are uniquely identified by “logical node IDs”.
A peer group (“PG”) is a collection of logical nodes, each of which exchanges information with other members of the group such that all members maintain an identical view of the group. Logical nodes are assigned to a particular peer group by being configured with the “peer group ID” for that peer group. Peer group IDs are specified at the time individual physical nodes are configured. Neighboring nodes exchange peer group IDs in “Hello packets”. If they have the same peer group ID then they belong to the same peer group.
Construction of a PNNI hierarchy begins by organizing the physical nodes (also referred to as “lowest level” nodes) of the network into a first level of peer groups. FIG. 2 shows network 100 of FIG. 1 organized into 7 peer groups 205a-g. In FIG. 2, peer group 205a is designated peer group “A.1.” Similarly, peer groups 205b-g are designated peer groups “A.2,” “A.3,” “A.4,” “B.1,” “B.2,” and “C,” respectively. A peer group is sometimes referred to herein by the letters “PG” followed by a peer group number. For example, “PG(A.2)” refers to peer group A.2 205b. Node and peer group numbering, such as A.3.2 and A.3, is an abstract representation used to help describe the relation between nodes and peer groups. For example the designation of “A.3.2” for node 1051 indicates that it is located in peer group A.3 205c. 
Logical Links
Under the PNNI protocol, logical nodes are connected by “logical links”. Between lowest level nodes, a logical link is either a physical link (such as links 110a-gg of FIG. 1) or a virtual private channel (“VPC”) between two lowest-level nodes. Logical links inside a peer group are sometimes referred to as “horizontal links” while links that connect two peer groups are referred to as “outside links”.
Information Exchange in PNNI
Each node in a PNNI network exchanges Hello packets with its immediate neighbors and thereby determines its local state information. This state information includes the identity and peer group membership of the node's immediate neighbors, and the status of its links to the neighbors. Each node bundles its state information in “PNNI Topology State Elements” (PTSEs), which are broadcast (“flooded”) throughout the peer group. A node's topology database consists of a collection of all PTSEs received, which together represent that node's present view of the PNNI routing domain. The topology database provides the information needed to compute a route from the given node to any address reachable in or through the routing domain.
Nodal Information
Every node generates a PTSE that describes its own identity and capabilities, information used to elect the peer group leader, as well as information used in establishing the PNNI hierarchy. This is referred to as the nodal information. Nodal information includes topology state information and reachability information.
Topology state information includes “link state parameters”, which describe the characteristics of logical links, and “nodal state parameters”, which describe the characteristics of nodes. Reachability information consists of addresses and address prefixes that describe the destinations to which calls may be routed via a particular node.
Initial Topology Database Exchange
When neighboring nodes being initialized through the exchange of Hellos conclude that they are in the same peer group, they proceed to synchronize their “topology databases”. Database synchronization is the exchange of information between neighbor nodes resulting in the two nodes having identical topology databases. The topology database includes detailed topology information about the peer group in which the logical node resides plus more abstract topology information representing the remainder of the PNNI routing domain.
Flooding
“Flooding” is the reliable hop-by-hop propagation of PTSEs throughout a peer group. Flooding ensures that each node in a peer group maintains an identical topology database. Flooding is an ongoing activity.
Peer Group Leader
A peer group is represented in the next higher hierarchical level as a single node called a “logical group node” or “LGN.” The functions needed to perform the role of a logical group node are executed by a node of the peer group, called the “peer group leader.” There is at most one active peer group leader (PGL) per peer group (more precisely at most one per partition in the case of a partitioned peer group). However, the function of peer group leader may be performed by different nodes at different times.
The particular node that functions as the peer group leader at any point in time is determined via a “peer group leader election” process. The criteria for election as peer group leader is a node's “leadership priority,” a parameter that is assigned to each physical node at configuration time. The node with highest leadership priority in a peer group becomes leader of that peer group. The election process is a continuously running protocol. When a node becomes active with a leadership priority higher than that of the current PGL, the election process transfers peer group leadership to the newly activated node. When a PGL is removed or fails, the node with the next highest leadership priority becomes PGL.
In the network of FIG. 2, the current PGL's are indicated by solid circles. Thus node A.1.3 105a is the peer group leader of peer group A.1 205a, node A.2.3 105x is the PGL of PG A.2 205b, node A.4.1 105f is the PGL of PG A.4 205d, node A.3.2 1051 is the PGL of PG A.3 205c, node B.1.1 105o is the PGL of PG B.1 205e, node B.2.3 105q is the PGL of PG B.2 205f, and node C.2 105v is the PGL of PG C 205g. 
Next Higher Hierarchical Level
The logical group node for a peer group represents that peer group as a single logical node in the next higher (“parent”) hierarchy level. FIG. 3 shows how peer groups 205a-g are represented by their respective LGN's in the next higher hierarchy level. In FIG. 3, PG(A.1) 205a is represented by logical group node A.1 305a, PG(A.2) 205b is represented by logical group node A.2 305b, PG(A.3) 205c is represented by logical group node A.3 305c, PG(A.4) 205d is represented by logical group node A.4 305d, PG(B.1) 205e is represented by logical group node B.1 305e, PG(B.2) 205f is represented by logical group node B.2 305f and PG(C) 205g is represented by logical group node C 305g. Through the use of peer groups and logical group nodes, the 26 physical nodes 105a-z of FIG. 1 can be represented by the seven logical nodes 305a-g of FIG. 3.
Logical nodes 305a-g of FIG. 3 may themselves be further grouped into peer groups. FIG. 4 shows one way that peer groups 205a-f of FIG. 2, represented by logical group nodes 305a-f of FIG. 3, can be organized into a next level of peer group hierarchy. It should be noted that it is not necessary for all peer groups at a level to be represented by logical group nodes in the next higher level.
In FIG. 4, peer groups A.1 205a, A.2 205b, A.3 205c, and A.4 205d have been grouped into peer group A 410a, and peer groups B.1 205e and B.2 205f have been grouped into peer group B 410b. Peer group C 205g is not represented by a logical group node at this level. Peer group A 410a is called the “parent peer group” of peer groups A.1 205a, A.2 205b, A.3 205c and A.4 205d. Conversely, peer groups A.1 205a, A.2 205b, A.3 205c and A.4 205d are called “child peer groups” of peer group A 410a. 
A parent peer group is identified by a peer group ID that is shorter in length than its child peer group IDs. Any node capable of becoming peer group leader should be configured with its parent peer group ID. The length of a peer group ID indicates the level of that peer group within the PNNI hierarchy.
Logical Group Node Functions
The functions of a logical group node are carried out by the peer group leader of the peer group represented by the logical group node. These functions include aggregating and summarizing information about its child peer group and flooding that information through its own peer group. A logical group node also passes information received from its peer group to the PGL of its child peer group for flooding. In addition, a logical group node may be a potential peer group leader of its own peer group. In that case, it should be configured so as to be able to function as a logical group node at one or more higher levels as well.
The manner in which a peer group is represented at higher hierarchy levels depends on the policies and algorithms of the peer group leader, which in turn are determined by the configuration of the physical node that functions as the peer group leader. To make sure that the peer group is represented in a consistent manner, all physical nodes that are potential peer group leaders should be consistently configured. However, some variation may occur if the physical nodes have different functional capabilities.
Peer groups function in the same manner at each hierarchy level. Thus higher level peer groups 410a-b of FIG. 4 are peer groups in the same manner as lower level peer groups 205a-g. The only difference is that each of its nodes represents a separate lower level peer group instead of a physical node. Just like peer groups 205a-g, peer group A 410a has a peer group leader (logical group node A.2 305b) chosen by the same leader election process used to elect leaders of lower level peer groups 205a-g. It should be noted that for logical group node A.2 305b to be able to function as the peer group leader for PG A 410a, the functions that define peer group leader of A should be provided to logical node A.2 305b, which is in turn implemented on lowest-level physical node A.2.3 105x (which is the current peer group leader for peer group A.2 205b). Accordingly, physical node A.2.3 105x should be configured not just to function as peer group leader for peer group A.2 205b, but also as the peer group leader for peer group A 410a. The same is true for any other potential peer group leaders of peer group A.2 205b. Furthermore, if any other nodes of peer group A 410a are potential peer group leaders (which is the usual case), all physical nodes that are potential peer group leaders of their child peer groups should be configured to function as peer group leader for peer group A 410a as well.
Progressing To The Highest Level Peer Group
The PNNI hierarchy is incomplete until the entire network is encompassed in a single highest level peer group. In the example of FIG. 4 this is achieved by configuring one more peer group 430 containing logical group nodes A 420a, B 420b and C 420c, which represent peer groups A 410a, B 410b, and C 205g, respectively. Another possible configuration would be if peer groups B 420b and C 205g were aggregated into a peer group BC which was then aggregated with peer group A 420a to form the highest level peer group. The network designer controls the hierarchy via configuration parameters that define the logical nodes and peer groups.
The hierarchical structure of a PNNI network is very flexible. The upper limit on successive, child/parent related peer groups is given by the maximum number of ever shorter address prefixes that can be derived from longest 13 octet address prefix. This equates to 104, which is adequate for most networks, since even international networks can typically be more than adequately configured with less than 10 levels of ancestry.
Recursion in the Hierarchy
The creation of a PNNI routing hierarchy can be viewed as the recursive generation of peer groups, beginning with a network of lowest-level nodes and ending with a single top-level peer group encompassing the entire PNNI routing domain. The hierarchical structure is determined by the way in which peer group IDs are associated with logical group nodes via configuration of the physical nodes.
Generally, the behavior of a peer group is independent of its level. However, the highest level peer group differs in that it does not need a peer group leader since there is no parent peer group for which representation by a peer group leader would be needed.
Address Summarization & Reachability
Address summarization reduces the amount of addressing information that needs to be distributed in a PNNI network. Address summarization is achieved by using a single “reachable address prefix” to represent a collection of end system and/or node addresses that begin with the given prefix. Reachable address prefixes can be either summary addresses or foreign addresses.
A “summary address” associated with a node is an address prefix that is either explicitly configured at that node or that takes on some default value. A summary address may be classified into “internal” and “exterior” reachability classes. An “interior” summary address is a summary address that relates to reachable addresses within the network. An “exterior” summary address is a summary address that relates to reachable addresses outside of the network.
A “foreign address” associated with a node is an address which does not match any of the node's summary addresses. By contrast a “native address” is an address that matches one of the node's summary addresses.
These concepts are clarified in the example depicted in FIG. 5 which is derived from FIG. 4. The attachments 505a-m to nodes A.2.1, A.2.2 and A.2.3 represent end systems. The alphanumeric associated with each end system represents that end system's ATM address. For example <A.2.3.2> associated with end system 505b represents an ATM address, and P<A.2.3>, P<A.2>, and P<A> represent successively shorter prefixes of that same ATM address.
An example of summary address information that can be used for each node in peer group A.2 of FIG. 5 is shown in Table 1:
TABLE 1Example Summary Address Lists for Nodes of PG(A.2)Summary Address ListSummary Address ListSummary Address Listfor A.2.1for A.2.2for A.2.3P<A.2.1>P<A.2.2>P<A.2.3>P<Y.2>P<Y.1>P<Z.2>
The summary address information in Table 1 represents instructions setting forth how each node should advertise address information for other nodes reachable via that node. For example, the first column of Table 1 indicates that node A.2.1 should advertise any addresses beginning with the prefix “A.2.1 ” as a single summarized address. The same is true for any addresses beginning with the prefix “Y.2”.
Summary address listings are not prescribed by the PNNI protocol but are a matter of the network manager's choice. For example, the summary address P<Y. 1.1> could have been used instead of P<Y. 1> at node A.2.2 or P<W> could have been included at node A.2.1. But P<A.2> could not have been chosen (instead of P<A.2.1> or P<A.2.3>) as a summary address at nodes A.2.1 and A.2.3 because a remote node selecting a route would not be able to differentiate between the end systems attached to A.2.3 and the end systems attached to A.2.1 (both of which include end systems having the prefix A.2). For the chosen summary address list at A.2.1, P<W.2.1.1> is a foreign address since it does not match any of the summary addresses of node A.2.1.
Moving up the next level in the hierarchy, logical group node A.2 requires its own list of summary addresses. Here again there are different alternatives that can be chosen. Because PG(A.2) is the ID of peer group A.2 it is reasonable to include P<A.2> in the summary address list (in some embodiments the peer group ID of an LGN is included in the LGN's summary address list as a default). Further, because summary addresses P<Y.1> and P<Y.2> can be further summarized by P<Y>, it also makes sense to configure P<Y> as a summary address. The resulting summary address list for logical group node A.2 is shown in Table 2:
TABLE 2Summary Address List for LGN A.2Summary Address Listfor LGN A.2P<A.2>P<Y>
Table 3 shows the reachable address prefixes advertised by each node in peer group A.2 according to their summary address lists of Table 1. A node advertises the summary addresses in its summary address list as well as foreign addresses (i.e. addresses not summarized in the summary address list) reachable through the node:
TABLE 3Advertised Reachable Addresses of Nodes in Peer Group A.2Reachable AddressesReachable AddressesReachable Addressesflooded by node A.2.1flooded by node A.2.2flooded by node A.2.3P<A.2.1>P<A.2.2>P<A.2.3>P<Y.2>P<Y.1>P<W.2.1.1>P<Z.2>
In the example of Table 3, node A.2.1 floods its summary addresses plus its foreign address whereas nodes A.2.2 and A.2.3 only issue their summary addresses since they lack any foreign addressed end systems.
Reachability information, i.e., reachable address prefixes (and foreign addresses), are fed throughout the PNNI routing hierarchy so that all nodes can reach the end systems with addresses summarized by these prefixes. A filtering is associated with this information flow that allows further summarization to increase scalability of the network. For example when LGN A.2 receives (via PGL A.2.3) the reachable address prefixes P<Y. 1> issued by node A.2.2 and P<Y.2> issued by node A.2.1 (see Table 3), it finds a match with its configured summary address P<Y>. LGN A.2 achieves a further summarization by advertising its single summary address P<Y> instead of separately advertising P<Y.1> and P<Y.2>.
Reachable address prefixes that cannot be further summarized by a LGN are advertised unmodified. For example when LGN A.2 receives the reachable address prefix P<Z.2> issued by A.2.2, the match against all its configured summary addresses (Table 2) fails, consequently LGN A.2 advertises P<Z.2> unmodified. Note that LGN A.2 views P<Z.2> as foreign since the match against all its configured summary addresses failed, even though P<Z.2> is a summary address from the perspective of node A.2.2. The resulting reachability information advertised by LGN A.2 is listed in Table 4:
TABLE 4Advertised Reachable Addresses of Node A.2Reachability information advertised byLGN A.2.P<A.2>P<Y>P<Z.2>P<W.2.1.1>
It should be noted that the reachability information advertised by node A.2.3 shown in Table 3 is different from that advertised by LGN A.2 shown in Table 4, even though node A.2.3 is PGL of peer group A.2. The reachability information advertised by LGN A.2 is the only reachability information about peer group A.2 available outside of the peer group, regardless of the reachability information broadcast by the peer group members themselves.
The relationship between LGN A and peer group leader A.2 is similar to the relationship between LGN A.2 and peer group leader A.2.3. If LGN A is configured without summary addresses, then it would advertise all reachable address prefixes that are flooded across peer group A into the highest peer group (including the entire list in Table 4). On the other hand if LGN A is configured with the default summary address P<A> (default because the ID of peer group A is PG(A)) then it will attempt to further summarize every reachable address prefix beginning with P<A> before advertising it. For example it will advertise the summary address P<A> instead of the address prefix P<A.2> (see Table 4) flooded by LGN A.2.
The ATM addresses of the logical nodes are subject to the same summarization rules as end system addresses. The reachability information (reachable address prefixes) issued by a specific PNNI node is advertised across and up successive (parent) peer groups, then down and across successive (child) peer groups to eventually reach all PNNI nodes lying outside the specified node.
Suppressed Summary Addresses
There is another filter mechanism that can be used with advertising of reachability information to limit the distribution of reachable address prefixes. This mechanism involves associating a “suppressed summary address” with the address(es) of end system(s) that inhibits an LGN from advertising the suppressed summary address. This option allows some addresses in the lower level peer group to be hidden from higher levels of the hierarchy, and hence other peer groups. This feature can be implemented for security reasons, making the presence of a particular end system address unknown outside a certain peer group.
Address suppression is implemented by including a “suppressed summary address” in the summary address list of a LGN. For example, in FIG. 5, assume that for security purposes, a network manager wishes to prevent the reachability of node A.2.1.2 505j from being advertised by LGN A.2.1 105y, yet still wants to advertise the reachability of nodes A.2.1.1 and A.2.1.3.
As shown in Table 1, the summary address list for LGN A.2.1 105y prior to suppression includes the default prefix P<A.2.1>. This means that as long as there are nodes in LGN A.2.1's child peer group whose prefixes match P<A.2.1>, LGN A.2.1 will advertise P<A.2.1> as a reachable address.
To suppress the reachability of node A.2.1.2, the network manager can add P<A.2.1> to the summary address list of LGN A.2.1 as a suppressed summary address, thereby causing LGN A.2.1 to not advertise reachability of any of its reachable nodes having the prefix P<A.2.1> (nodes A.2.1.1 505i, A.2.1.2 505j and A.2.1.3 505k). Note that adding P<A.2.1.2> as a suppressed summary address would not have been sufficient. The existence of nodes A.2.1.1 505i and A.2.1.3 505k would still cause LGN A.2.1 to advertise reachability of P<A.2.1>, because even with node A.2.1.2 suppressed, these remaining nodes would match LGN A.2.1's summary address P<A.2.1>, thereby causing the summary address P<A.2.1> to be advertised.
Although adding suppressed summary address P<A.2.1> to LGN A.2.1's summary address list achieves the goal of suppressing advertising the reachability of node A.2.1.2, it has the unintended effect of suppressing advertising the reachability of nodes A.2.1.1 and A.2.1.3 as well. To allow the reachability of nodes A.2.1.1 and A.2.1.3 to be advertised by LGN A.2.1, these addresses can be explicitly added to LGN A.2.1's summary address list. Table 5 shows the summary address list for LGN A.2.1 before and after adding suppression of the reachability of node A.2.1.2:
TABLE 5Suppressing Reachability of Node A.2.1.2Summary address list forSummary address list fornode A.2.1 w/o suppressionnode A.2.1 w/suppressionof A.2.1.2of A.2.1.2P<A.2.1>DefaultP<A.2.1>SuppressedP<Y.2>P<Y.2>P<W.2.1.1>P<W.2.1.1>P<A.2.1.1>P<A.2.1.3>
An entry having the longest prefix match with one or more nodes in the child peer group takes precedence over entries having a shorter prefix match. Accordingly, each summary address in an LGN's summary address list must have a unique prefix. For example, a summary address list may not contain a summary address and a suppressed summary address with the same prefix. The only time the same prefix may be used in two entries in a summary address list is if the list uses the “internal” and “exterior” reachability classes. In that case, two summary addresses may have the same prefix, but only if one is designated to be an “internal” summary address and the other an “exterior” summary address. However, prefixes within each reachability class must still be unique.
In Table 5, the explicit entries for P<A.2.1.1> and P<A.2.1.3> have longer prefixes than suppressed summary address entry for P<A.2.1>. Accordingly, the explicit entries for P<A.2.1.1> and P<A.2.1.3> take precedence over suppressed summary address entry for P<A.2.1>. The resulting addresses advertised by LGN A.2.1 are shown in Table 6:
TABLE 6Advertised Reachable Addresses of Node A.2.1 w/suppressionReachability information advertised byLGN A.2.1P<Y.2>P<W.2.1.1>P<A.2.1.1>P<A.2.1.3>Address Scoping
Reachability information advertised by a logical node always has a scope associated with it. The scope denotes a level in the PNNI routing hierarchy, and it is the highest level at which this address can be advertised or summarized. If an address has a scope indicating a level lower than the level of the node, the node will not advertise the address. If the scope indicates a level that is equal to or higher than the level of the node, the address will be advertised in the node's peer group.
When summarizing addresses, the address to be summarized with the highest scope will determine the scope of the summary address. The same rule applies to group addresses, i.e. if two or more nodes in a peer group advertise reachability to the same group address but with different scope, their parent node will advertise reachability to the group address with the highest scope.
It should be noted that rules related to address suppression take precedence over those for scope. That is, if the summary address list for an LGN contains an address suppression, that address is not advertised even if the scope associated with the address is higher than the level of the LGN.
Effect of Summarizing Reachability
Although using summary addresses reduces the amount of address information that needs to be propagated, it also reduces the amount of detail available for specific addresses. By aggregating parameters of the addresses that are summarized, details for specific addresses are hidden in the summarized address information.
At times, however, a network manager may wish to provide detailed reachability information for a particular node that has a prefix for which a summary address has been configured. For example, assume that node Y.1.1.3 505f of FIG. 5 has an external connection to a media gateway that warrants separate advertisement. Under the PNNI protocol, the addresses of reachable nodes in a peer group having a common prefix can be advertised in two ways: 1) by a summary address that aggregates reachabilitiy information for all nodes with the common prefix; or 2) by separate, explicit advertisement for each node with the common prefix. To separately advertise reachability information for node Y.1.1.3 505f of FIG. 5 the reachability information for the other nodes in the same peer group sharing the same prefix (namely nodes Y.1.1.1 505d and Y.1.1.2 505e) must be separately explicitly advertised as well. This leads to inefficient use of network bandwidth, because more detailed reachability information is broadcast than is actually needed.